import collections
import functools
# class Solution:
#     def beautifulSubsets(self, nums, k: int) -> int:
#         d = collections.Counter(nums)
#         base_ans = 0
#         nums = []
#         for val in d:
#             if val + k not in d and val - k not in d:
#                 base_ans += d[val]
#             else:
#                 nums += [val] * d[val]
#         base_ans = 2 ** base_ans
#         n = len(nums)
#         a = set()
#         for i in range(n):
#             for j in range(i + 1, n):
#                 if abs(nums[i] - nums[j]) == k:
#                     a.add((1 << i) + (1 << j))
#         @functools.cache
#         def cal(val):
#             left_val = val & (val - 1)
#             if left_val == 0:
#                 return True
#             if cal(left_val):
#                 last_val = val - left_val
#                 while left_val > 0:
#                     now_last_val = left_val & (-left_val)
#                     if now_last_val | last_val in a:
#                         return False
#                     left_val = left_val & (left_val - 1)
#                 return True
#             else:
#                 return False
#         ans = 0
#         for val in range(1, 2 ** n):
#             ans += cal(val)
#         return ans * base_ans + base_ans - 1
class Solution:
    def beautifulSubsets(self, nums, k: int) -> int:
        st = collections.defaultdict(int)
        self.ans = 0
        def dfs(i):
            if i < len(nums):
                if st[nums[i] + k] or st[nums[i] - k]:
                    dfs(i + 1)
                else:
                    dfs(i + 1)
                    st[nums[i]] += 1
                    self.ans += 1
                    dfs(i + 1)
                    st[nums[i]] -= 1
        dfs(0)
        return self.ans


data = Solution()
nums = [1, 2, 3, 3]
k = 1
print(data.beautifulSubsets(nums, k))